n=1998;
bracket=["(",")",")",")","(","(","(",")","(","(","(",")","(","(",")",")",")",")",")","(",")","(","(","(",")",")","(",")","(",")",")","(",")",")","(","(","(","(","(",")",")",")","(","(","(","(","(",")","(",")","(","(","(","(","(","(","(",")",")","(",")",")",")",")","(","(","(",")",")",")","(",")","(",")",")",")","(","(",")",")","(",")","(","(","(",")",")",")",")",")","(",")","(","(",")",")","(","(",")","(",")","(",")","(","(",")","(",")","(",")",")","(",")",")",")","(",")",")","(","(","(","(","(",")",")",")",")","(","(",")","(","(",")","(",")","(","(",")",")",")",")",")","(",")",")","(","(","(",")",")",")","(","(","(","(",")","(","(","(","(","(",")",")","(","(","(","(",")","(","(","(","(","(",")","(",")",")",")","(",")",")","(","(",")",")",")",")",")","(","(","(",")",")","(",")","(",")","(",")","(",")","(",")","(","(","(","(","(","(",")","(",")","(",")",")",")",")",")",")","(","(","(",")","(",")",")","(","(","(","(",")","(",")","(",")","(",")",")","(",")",")",")",")",")","(",")",")","(",")",")","(","(","(","(","(","(","(",")",")",")","(","(","(","(",")","(",")",")","(","(",")",")",")",")",")","(",")",")",")",")",")","(",")","(",")","(",")","(","(","(","(",")",")",")","(",")",")","(",")","(","(","(","(","(","(","(",")",")","(",")",")","(",")",")",")",")","(","(",")",")",")","(",")",")",")","(",")",")","(",")","(",")","(","(","(","(",")","(","(",")","(","(","(","(",")",")",")","(","(",")",")","(","(",")","(","(",")","(","(","(","(","(","(","(",")",")",")",")","(","(",")",")",")",")",")",")",")",")",")","(",")",")",")","(",")","(","(",")",")",")","(","(","(",")",")","(",")",")",")","(","(",")",")",")",")",")",")",")",")",")","(",")",")","(","(","(",")",")","(",")","(","(",")",")","(",")",")",")","(",")","(",")",")","(",")","(","(","(","(","(","(","(","(",")",")","(","(","(","(",")","(",")","(","(","(","(",")","(","(","(","(",")","(","(",")",")",")","(","(",")","(",")","(",")",")","(","(","(",")","(",")",")","(","(","(",")",")","(","(","(",")",")",")",")",")",")",")",")","(","(",")",")","(","(","(",")","(",")","(","(","(","(","(","(","(","(","(","(",")","(","(","(","(","(","(","(","(","(",")",")",")",")","(","(",")",")","(","(",")","(",")",")",")",")","(","(","(",")","(","(","(",")",")","(","(","(",")",")",")",")",")",")","(","(",")","(","(","(",")",")",")",")",")","(",")","(",")","(","(","(","(","(","(","(",")",")","(",")",")","(","(","(",")",")",")",")","(",")","(","(",")",")","(",")","(",")","(","(","(",")","(",")","(",")",")","(","(","(",")","(",")","(",")",")","(","(",")",")","(",")","(","(",")",")","(","(",")",")",")",")",")","(",")",")",")",")","(","(","(","(",")",")",")","(",")","(",")","(","(","(","(",")",")","(","(","(",")","(","(",")","(","(",")",")","(",")",")","(","(",")",")","(",")","(",")",")",")",")","(",")","(",")",")","(","(","(",")","(","(","(",")",")","(",")",")",")",")","(","(","(","(",")",")","(","(","(","(","(","(","(","(","(","(",")",")","(","(","(",")",")",")",")","(","(",")","(",")",")",")","(","(","(","(",")",")",")","(",")",")",")","(","(","(",")","(",")","(","(","(",")","(","(",")",")","(","(",")","(","(",")",")","(",")",")","(",")",")",")",")",")",")","(",")",")",")","(",")","(",")","(","(",")",")",")",")","(","(",")",")",")","(","(","(","(","(",")","(","(",")",")",")","(","(",")","(","(","(","(","(",")",")",")",")",")",")",")",")","(","(",")",")",")","(","(","(",")",")",")",")",")",")",")","(",")",")",")","(","(","(",")","(","(","(","(",")","(",")",")","(","(",")","(","(",")",")",")",")",")",")",")","(","(",")",")","(",")","(",")",")",")","(","(",")",")","(",")","(","(",")",")",")",")","(","(",")",")","(","(",")","(","(","(",")",")",")","(",")","(",")",")","(","(",")","(","(","(","(",")",")","(","(",")",")",")","(",")",")",")","(","(","(","(",")",")","(",")","(","(","(","(",")","(",")",")",")","(","(",")",")","(","(","(","(","(","(",")",")",")",")","(","(","(",")","(","(","(",")","(","(","(",")","(",")","(","(","(",")",")","(",")","(",")","(",")",")","(",")",")","(",")","(",")","(",")","(","(","(","(",")",")","(",")","(","(","(",")",")",")",")","(",")","(",")",")","(",")","(","(",")",")","(","(",")","(","(","(",")","(","(",")","(",")",")","(","(",")","(",")",")",")","(",")","(","(",")","(","(","(",")","(","(",")","(","(","(",")","(","(","(",")","(","(",")","(",")","(","(","(","(","(","(","(",")","(",")",")",")",")",")",")","(","(",")",")","(","(","(",")",")",")",")","(","(",")","(","(","(",")","(","(",")",")",")",")","(",")",")","(",")",")",")",")",")",")",")","(",")","(","(",")",")","(",")","(","(","(","(",")","(",")","(","(",")","(","(",")",")",")","(",")",")","(",")",")",")","(","(",")",")",")",")",")","(",")",")",")","(","(","(","(","(",")",")","(",")",")","(",")",")","(",")",")",")","(","(",")",")",")",")",")","(","(","(",")","(","(","(","(",")",")",")","(",")",")",")",")",")",")",")",")","(","(","(","(",")",")",")",")",")",")",")","(","(","(",")","(",")","(",")",")","(",")","(","(",")",")",")","(",")",")","(","(","(",")",")","(",")",")","(","(","(",")",")",")","(",")","(",")","(","(",")",")","(",")",")",")",")",")","(",")",")",")","(",")","(","(","(","(",")","(",")","(","(","(","(",")","(","(",")","(",")","(","(",")","(","(",")","(","(","(","(",")","(",")",")",")","(","(",")","(",")",")",")","(","(",")",")","(","(",")",")","(","(","(","(",")","(","(","(",")",")",")",")",")",")",")",")",")",")",")","(",")","(",")",")",")",")",")","(","(",")","(",")",")","(",")",")",")","(",")",")",")",")","(",")","(","(",")","(","(","(",")",")",")",")",")",")",")",")",")","(",")","(",")",")",")",")","(",")","(","(","(","(","(",")","(",")","(",")","(","(","(",")","(","(",")","(","(","(","(","(",")","(","(",")",")","(",")","(",")",")",")","(","(","(","(","(",")",")","(","(","(",")","(",")","(",")","(",")","(",")",")","(",")","(",")",")",")",")","(",")",")","(","(",")",")",")","(",")","(",")",")",")",")","(","(","(","(",")","(",")","(","(",")","(",")",")","(","(",")",")","(","(","(","(","(","(","(",")",")",")",")",")","(",")","(",")","(","(",")",")","(","(",")","(",")",")","(","(","(",")","(","(","(",")",")",")",")","(",")",")",")",")",")","(",")","(","(","(",")","(","(",")","(","(","(","(",")","(","(","(","(",")",")",")","(",")",")","(",")",")","(",")",")","(","(",")",")",")","(","(","(",")","(",")",")",")",")",")","(","(","(",")","(",")",")",")",")",")","(",")",")",")",")",")","(","(",")",")","(","(","(","(",")",")","(",")",")","(",")",")",")","(",")",")","(","(",")",")","(",")",")",")",")","(",")",")",")","(",")",")",")","(","(",")","(",")",")","(",")",")","(",")",")",")",")","(","(","(","(",")","(",")",")","(","(","(","(","(",")","(","(",")",")",")","(","(","(","(","(","(",")",")","(",")",")",")","(","(","(","(",")",")","(",")","(",")","(","(","(","(",")","(",")","(","(","(",")",")",")","(","(",")",")","(",")",")","(",")",")",")","(",")",")",")",")","(",")",")",")","(","(","(",")","(",")",")",")",")",")","(",")",")","(",")","(",")",")",")",")",")",")","(",")",")","(","(","(","(","(",")",")",")","(","(",")","(","(",")","(","(","(","(","(","(","(",")","(",")",")","(",")",")",")","(",")","(",")",")",")","(",")",")","(","(","(","(",")",")",")","(",")","(","(","(",")",")",")","(",")",")",")","(","(",")",")","(","(",")","(","(","(","(",")",")",")","(",")",")",")",")",")",")","(","(","(",")","(","(","(",")",")",")","(","(",")","(",")",")","(",")","(",")","(","(",")",")","(",")",")","(",")",")","(",")","(",")",")","(",")","(","(",")","(",")","(",")","(","(",")",")","(","(",")","(","(",")","(",")","(","(","(","(",")",")","(","(",")","(",")",")","(","(",")",")","(","(",")",")","(",")",")",")",")",")","(","(","(",")","(",")",")",")","(",")",")","(","(",")",")",")","(","(","(","(",")","(","(",")","(",")","(",")",")","(",")",")",")","(",")","(","(",")","(","(",")","(",")",")","(",")",")",")",")","(",")",")",")","(",")",")","(","(",")","(",")",")","(",")",")",")","(","(",")",")",")","(","(",")","(","(","(","(","(","(",")","(","(","(",")","(","(","(","(","(","(","(","(",")",")","(",")","(","(","(",")","(",")","(",")","(",")","(",")",")",")",")","("];
father=[1,2,1,3,2,6,3,4,5,6,5,12,13,3,1,3,11,17,6,6,2,5,22,20,9,21,21,7,1,3,17,10,7,19,21,29,31,26,11,7,12,1,15,22,7,3,8,43,6,7,43,48,11,37,46,17,36,1,30,41,25,58,20,41,22,26,14,27,20,28,63,9,31,6,30,44,35,55,30,12,23,76,75,37,59,28,17,49,49,3,80,53,43,85,6,19,86,95,66,16,68,74,59,103,97,83,91,27,83,33,74,46,110,1,6,78,61,65,30,102,103,40,120,82,17,125,81,43,115,3,91,68,91,119,33,68,27,119,83,62,42,98,119,133,28,142,12,122,30,19,114,5,66,51,70,20,3,42,63,75,152,102,82,11,68,161,68,121,169,111,57,97,89,134,129,24,88,162,84,121,22,9,154,20,22,166,104,139,168,76,65,163,140,146,147,167,44,129,50,32,154,92,64,55,16,79,187,61,82,2,208,150,191,27,75,99,137,97,209,206,182,149,112,77,190,57,1,197,197,31,39,114,32,166,215,134,34,55,14,149,146,181,45,13,99,56,176,246,27,32,156,242,121,195,155,158,124,214,253,242,33,188,213,11,231,42,101,140,33,181,40,3,84,46,76,144,169,172,121,47,45,41,176,210,7,57,20,46,92,245,104,251,119,59,32,59,167,196,1,83,44,277,277,128,277,105,123,271,73,100,205,226,122,57,56,143,223,271,154,21,293,96,150,176,150,146,45,35,171,32,284,328,332,189,295,6,78,123,138,79,202,239,148,60,201,264,216,75,251,309,261,84,126,218,273,95,106,16,62,293,276,293,238,193,216,366,56,136,219,302,123,290,3,128,348,159,8,7,165,269,62,58,376,361,121,196,300,362,339,212,116,1,58,129,86,221,287,381,81,300,56,276,97,397,188,290,274,333,101,60,1,248,106,161,412,332,51,409,251,300,185,267,312,59,305,124,90,109,394,185,53,89,335,324,58,350,389,39,213,190,317,437,3,427,430,38,134,130,360,382,152,305,352,84,322,23,420,425,438,17,444,328,129,234,230,172,174,134,130,105,60,442,239,443,74,46,406,203,200,73,119,455,209,414,31,403,397,309,246,64,480,110,192,339,141,47,448,184,447,456,188,469,353,84,185,390,458,272,479,316,422,346,506,366,284,140,231,232,129,120,45,304,137,17,397,232,126,335,312,95,271,138,416,95,335,343,405,26,536,458,56,85,202,32,46,167,373,73,359,75,205,452,241,233,288,458,316,212,390,160,408,134,276,506,473,189,515,245,33,53,360,524,7,490,249,264,60,155,342,437,467,453,124,429,173,21,203,482,520,402,388,113,486,223,334,574,572,217,342,408,257,298,165,85,30,287,240,599,393,391,137,128,584,291,122,140,360,495,93,429,515,254,415,384,476,542,396,271,507,543,627,278,210,94,593,136,623,377,305,297,159,101,290,64,219,149,363,383,348,563,415,617,208,458,191,14,462,519,434,107,321,264,596,468,643,304,502,69,254,333,350,89,585,158,588,547,299,282,525,452,92,594,17,288,445,372,662,157,153,607,184,566,249,611,224,298,613,179,140,411,466,180,180,27,639,559,26,702,605,582,430,536,581,667,337,44,166,536,401,251,639,585,645,209,315,418,164,437,521,680,215,117,129,472,131,570,681,316,698,447,269,299,70,718,700,292,257,653,691,577,2,745,526,745,540,739,652,85,751,724,199,252,678,36,265,128,742,290,234,252,108,172,325,631,758,297,350,513,740,20,311,165,584,111,200,259,150,143,638,371,437,657,160,304,227,709,108,139,749,300,729,204,198,784,349,311,403,395,102,564,762,180,169,550,425,443,479,659,732,537,258,682,748,817,686,251,463,208,531,456,641,760,445,705,349,147,270,18,450,18,14,528,365,755,356,840,113,631,727,233,149,731,644,741,837,381,579,575,334,519,164,643,259,632,433,289,248,346,632,225,56,131,526,597,350,107,630,319,407,545,302,869,176,419,349,116,593,876,526,837,630,136,412,412,537,633,757,751,396,155,333,373,790,381,886,592,566,883,841,649,250,291,535,380,379,657,759,1,722,530,870,606,537,491,787,702,7,17,392,672,600,419,65,518,183,763,626,637,575,18,24,652,52,447,649,106,64,259,693,239,65,228,807,821,304,308,360,230,528,312,257,665,527,515,787,834,461,698,816,731,99,334,695,493,670,76,346,419,224,933,21,338,699,44,569,755,182,14,336,85,165,814,638,835,272,223,351,824,809,330,281,802,929,916,361,411,943,616,895,937,675,765,700,913,252,408,466,309,842,846,50,110,961,74,283,309,501,747,814,523,763,411,688,19,995,849,63,841,355,334,171,268,762,779,968,186,782,613,104,967,692,513,748,740,799,320,655,980,658,770,70,1032,19,13,15,80,31,269,730,308,254,647,1041,1039,386,551,297,695,1052,278,389,864,375,109,154,767,657,690,8,746,21,746,660,743,49,430,777,774,140,734,89,85,295,277,785,1031,273,746,892,749,327,780,916,464,913,138,345,372,616,175,527,400,371,123,986,808,552,1024,995,894,738,809,74,1089,309,298,489,339,966,956,836,454,8,1054,446,1015,150,852,92,503,36,662,1050,871,742,927,750,1046,736,911,763,1135,362,343,232,301,949,327,760,239,652,427,441,708,273,890,585,1040,590,538,378,588,32,40,281,655,103,400,762,924,150,758,319,770,1131,288,335,948,688,554,189,1044,599,474,988,629,647,1173,532,135,663,609,814,1040,1144,450,1095,170,1125,239,574,1083,1033,666,178,1034,612,85,368,339,1025,101,740,429,692,839,434,477,833,326,113,882,296,1019,1221,931,866,829,180,1072,1057,165,470,167,780,710,721,719,50,1061,217,252,431,1106,99,891,228,1039,624,1214,747,757,473,73,1248,768,216,880,598,1076,408,732,683,788,1162,502,924,703,712,889,661,832,603,214,259,639,663,591,812,1132,725,89,1155,995,1239,983,1093,647,1033,511,293,973,511,140,136,326,463,1219,969,854,608,1083,841,505,1105,980,639,1019,537,232,823,59,1266,1289,1170,1303,466,680,63,839,481,477,306,456,368,1203,1164,131,1258,1079,828,865,317,1045,881,144,1060,1240,13,1275,41,1361,479,1031,335,814,1267,838,292,1075,33,237,43,1222,811,1304,305,1253,762,1262,1210,524,249,719,855,506,821,520,686,385,800,194,886,1324,468,515,1239,764,393,148,1045,1027,273,599,1146,118,1211,176,1256,1342,247,1200,187,1002,412,139,876,617,317,341,517,79,251,789,1403,199,1099,1224,807,995,799,996,1218,594,245,1326,232,470,827,719,1334,358,110,655,1182,1370,840,215,1133,882,1295,943,813,811,884,863,111,390,1410,1365,1188,319,540,1070,465,1418,925,387,847,181,262,779,636,284,755,433,701,1272,666,951,625,1423,813,504,1427,555,362,276,461,172,320,1465,671,1058,1364,160,518,434,93,1233,161,1040,920,1482,72,880,999,1048,1174,46,1487,1098,80,624,1443,566,583,535,1320,468,356,428,1379,337,430,1493,1028,942,21,971,1219,1110,1020,1083,13,769,533,915,969,528,994,667,79,113,206,1268,1259,269,1028,114,4,349,922,1206,1201,241,402,645,1317,1448,642,562,1441,699,1069,944,1180,943,1342,1398,763,546,879,817,37,1503,750,1066,1209,423,897,1385,401,851,880,55,1312,1315,832,243,991,168,865,1429,67,1011,1126,1100,1581,1225,736,1089,466,742,1018,1024,727,1084,1391,234,650,378,1416,1564,1276,899,263,115,174,249,1264,332,645,1219,1014,29,1596,1577,563,562,1264,1140,197,1477,683,1228,104,804,415,1005,768,206,774,17,1183,1479,737,117,512,29,91,747,1558,818,368,1296,777,204,178,535,859,1482,1271,895,1347,1280,1641,362,1613,671,241,1549,1607,1667,788,655,124,462,1491,42,933,1027,121,963,154,199,970,741,850,434,227,1053,1067,408,530,1323,324,4,1517,1305,637,315,1281,1050,182,663,227,1089,1338,997,687,880,660,350,763,1287,643,1126,1353,144,517,1586,826,68,1123,853,848,550,626,1353,1271,654,195,204,1262,1255,1683,665,295,383,1170,637,152,835,1536,28,1022,916,330,1742,906,708,541,1515,1700,1427,1728,1676,1244,181,1455,784,607,748,963,98,1399,14,1319,1088,1747,1432,1342,1745,514,1435,1200,1248,798,757,182,1655,940,551,1191,1648,1453,1455,1661,196,1658,1788,486,40,61,726,162,164,383,410,52,1782,1346,1151,797,618,1710,67,638,45,1688,108,795,140,334,1321,76,864,1665,1783,256,376,875,875,708,346,350,664,1075,223,37,358,1276,445,1488,43,1104,467,888,697,510,1088,102,157,547,1146,1344,1184,1770,1023,78,928,927,1660,837,617,86,236,170,534,1698,969,606,1430,1693,913,105,1015,242,1737,609,1765,1023,1348,756,1006,525,995,1241,1754,585,595,1634,1167,1403,1403,304,382,1668,624,939,1779,1884,1532,626,1771,1510,622,1109,470,1863,1097,1889,1040,1512,500,348,855,875,1174,523,1504,239,1826,796,1874,306,446,602,757,1059,1422,442,891,427,73,1278,350,677,599,1689,1138,368,1044,653,507,1644,742,99,326,572,320,1770,1174,1151,575,617,197,568,608,1795,1563,146,1450,1911,629,401,600,1129,552,1725,600,955,1113,716,510,834,15,1514,57,495,525,1331,455,93,401,1503,1795,1329,952,910,875,1370,1525,1003,50,738,919,892,727,1307,35,1381,107,577,1505,98];